1. Field of the Invention
The present invention pertains generally to ad hoc networking, and more particularly to a method and system of medium access control (MAC) to provide collision-free access within the ad hoc network.
2. Description of the Background Art
A number of scheduling methods exist for controlling time division multiple access (TDMA) to achieve collision-free transmissions of data frames within time-slots of a single communication channel in a multi-hop packet radio network. These methods generally require that each node in the network utilize a certain amount of bandwidth to resolve contentions for a given time-slot before transmissions on that time-slot.
It has been shown that the problem of scheduling optimal time division multiplexing (TDM) for broadcasting channel access in multi-hop packet radio networks is an NP-complete problem even when global topology knowledge is made available to all nodes within the network. Distributed algorithms, therefore, have been proposed that eliminate direct packet interference, also referred to as primary conflict, and hidden terminal interference, also referred to as secondary conflict, within the transmission segment of the channel by splitting out a second contention-based control segment from the channel for out-band signaling of time-slot allocation information. However, it will be appreciated that the technique suffers from a considerable amount of overhead due to the use of a control segment. Several channel scheduling and reservation methods (protocols) have been proposed which are based on in-band signaling, such as phased dialogs or RTS/CTS handshakes, which occur before packet transmission. The limiting factor within this class of scheduling protocols is that they spend a portion of the channel for channel contention, and such contention may result in unused time-slots, as a result of unresolved contentions.
A number of topology-transparent scheduling methods have been proposed which conceptually allow a node to transmit in a number of time-slots in each frame. The allowed transmission times are given as time-slots within the given block. When a node i transmits in a frame corresponding to a unique code such that, for any given neighbor k of i, node i has at least one transmission slot during which k and none of k's own neighbors are transmitting. Therefore; within any given framing time, any neighbor of node i can receive at least one collision-free packet from i. Substantial limitations have hindered these previous topology-independent scheduling approaches, such as: (a) the sender of the packet is responsible to recognize which neighbor, or neighbors, are able to correctly receive the packet in a given slot. This requirement implies that the sender needs to transmit the packet in the various slots it has available in a frame, and (b) the frame length, given by a number of slots, must be larger than the number of nodes in a two-hop neighborhood and it depends on the network size, which is less scalable. It will be appreciated that these protocols are subject to similar limitations in that they either compete with two-hop neighbors for collision-free channel access or allow collisions to occur and then amend with repetitions.
Therefore, a need exists for a method and system that allows collision-free channel access within an ad hoc network while maximizing the use of the available channel bandwidth. The present invention satisfies those needs, as well as others, and overcomes the deficiencies of previously developed medium access control protocols.